<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html
  PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xml:lang="zh" lang="zh">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8"/>
<meta name="DC.Type" content="concept"/>
<meta name="DC.Title" content="Lucene的基本规则"/>
<meta name="DC.subject" content="Apache, Lucene, 指南, OSSEZ, OSS 计算技术"/>
<meta name="keywords" content="Apache, Lucene, 指南, OSSEZ, OSS 计算技术"/>
<meta name="DC.Relation" scheme="URI" content="../../tasks/chapter02/chapter02.html"/>
<meta name="prodname" content="Lucene 指南"/>
<meta name="version" content="1.0.0.0"/>
<meta name="brand" content="OSSEZ APACHE LUCENE"/>
<meta name="copyright" content="OSSEZ (中国) 信息技术有限公司 2006, 2012" type="primary"/>
<meta name="DC.Rights.Owner" content="OSSEZ (中国) 信息技术有限公司 2006, 2012" type="primary"/>
<meta name="DC.Format" content="XHTML"/>
<meta name="DC.Identifier" content="chapter01"/>
<meta name="DC.Language" content="zh"/>
<link rel="stylesheet" type="text/css" href="../../css/commonltr.css"/>
<link rel="stylesheet" type="text/css" href="../../css/public.css"/>
<title>Lucene的基本规则</title>
<svg:script xmlns:syntaxdiagram-svg="http://www.moldflow.com/2006/syntaxdiagram-svg" xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" type="text/ecmascript" xlink:href="../../js/constants.js"/><svg:script xmlns:syntaxdiagram-svg="http://www.moldflow.com/2006/syntaxdiagram-svg" xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" type="text/ecmascript" xlink:href="../../js/diagram.js"/><svg:script xmlns:syntaxdiagram-svg="http://www.moldflow.com/2006/syntaxdiagram-svg" xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" type="text/ecmascript" xlink:href="../../js/sequence.js"/><svg:script xmlns:syntaxdiagram-svg="http://www.moldflow.com/2006/syntaxdiagram-svg" xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" type="text/ecmascript" xlink:href="../../js/loop.js"/><svg:script xmlns:syntaxdiagram-svg="http://www.moldflow.com/2006/syntaxdiagram-svg" xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" type="text/ecmascript" xlink:href="../../js/decision.js"/><svg:script xmlns:syntaxdiagram-svg="http://www.moldflow.com/2006/syntaxdiagram-svg" xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" type="text/ecmascript" xlink:href="../../js/revdecision.js"/><svg:script xmlns:syntaxdiagram-svg="http://www.moldflow.com/2006/syntaxdiagram-svg" xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" type="text/ecmascript" xlink:href="../../js/boxed.js"/><svg:script xmlns:syntaxdiagram-svg="http://www.moldflow.com/2006/syntaxdiagram-svg" xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" type="text/ecmascript" xlink:href="../../js/unboxed.js"/><svg:script xmlns:syntaxdiagram-svg="http://www.moldflow.com/2006/syntaxdiagram-svg" xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" type="text/ecmascript" xlink:href="../../js/text.js"/><svg:script xmlns:syntaxdiagram-svg="http://www.moldflow.com/2006/syntaxdiagram-svg" xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" type="text/ecmascript" xlink:href="../../js/void.js"/><svg:script xmlns:syntaxdiagram-svg="http://www.moldflow.com/2006/syntaxdiagram-svg" xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" type="text/ecmascript" xlink:href="../../js/notecontainer.js"/><svg:script xmlns:syntaxdiagram-svg="http://www.moldflow.com/2006/syntaxdiagram-svg" xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" type="text/ecmascript" xlink:href="../../js/note.js"/><svg:script xmlns:syntaxdiagram-svg="http://www.moldflow.com/2006/syntaxdiagram-svg" xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" type="text/ecmascript" xlink:href="../../js/main.js"/><link rel="stylesheet" type="text/css" href="css/syntaxdiagram.css"/></head>
<body id="chapter01">


  <h1 class="title topictitle1">Lucene的基本规则</h1>

  
  <div class="body conbody">
    <p class="p">Lucene 为了使的信息的存储占用的空间更小，访问速度更快，采取了一些特殊的技巧，然而在看Lucene 文件格式的时候，这些技巧却容易使我们感到困惑，所以有必要把这些特殊的技巧规则提取出来介绍一下。</p>

    <div class="section"><h2 class="title sectiontitle">前缀后缀规则(Prefix+Suffix)</h2>
      
      <p class="p">Lucene 在反向索引中，要保存词典(Term Dictionary)的信息，所有的词(Term)在词典中是按照字典顺序进行排列的，然而词典中包含了文档中的几乎所有的词，并且有的词还是非常的长的，这样索引文件会非常的大，所谓前缀后缀规则，即当某个词和前一个词有共同的前缀的时候，后面的词仅仅保存前缀在词中的偏移(offset)，以及除前缀以外的字符串(称为后缀)。</p>

      <p class="p"><img class="image" src="../../images/chapter02_03_image01.png" alt="存储结构"/></p>

      <p class="p">比如要存储如下词:term，termagancy，termagant，terminal，</p>

      <p class="p">如果按照正常方式来存储，需要的空间如下：</p>

      <p class="p">[VInt = 4] [t][e][r][m]，[VInt = 10][t][e][r][m][a][g][a][n][c][y]，[VInt = 9][t][e][r][m][a][g][a][n][t]，[VInt = 8][t][e][r][m][i][n][a][l]</p>

      <p class="p">共需要35 个Byte。</p>

      <p class="p">如果应用前缀后缀规则，需要的空间如下：</p>

      <p class="p">[VInt = 4] [t][e][r][m]，[VInt = 4 (offset)][VInt = 6][a][g][a][n][c][y]，[VInt = 8 (offset)][VInt = 1][t]，[VInt = 4(offset)][VInt = 4][i][n][a][l]</p>

      <p class="p">共需要22 个Byte。</p>

      <p class="p">大大缩小了存储空间，尤其是在按字典顺序排序的情况下，前缀的重合率大大提高。</p>

    </div>

    <div class="section"><h2 class="title sectiontitle">差值规则(Delta)</h2>
      
      <p class="p">在Lucene 的反向索引中，需要保存很多整型数字的信息，比如文档ID 号，比如词(Term)在文档中的位置等等。</p>

      <p class="p">我们知道，整型数字是以VInt 的格式存储的。随着数值的增大，每个数字占用的Byte 的个数也逐渐的增多。所谓差值规则(Delta)就是先后保存两个整数的时候，后面的整数仅仅保存和前面整数的差即可。</p>

      <p class="p"><img class="image" src="../../images/chapter02_03_image02.png" alt="差值规则"/></p>

      <p class="p">比如要存储如下整数：16386，16387，16388，16389</p>

      <p class="p">如果按照正常方式来存储，需要的空间如下：</p>

      <p class="p">[(1) 000, 0010][(1) 000, 0000][(0) 000, 0001]，[(1) 000, 0011][(1) 000, 0000][(0) 000, 0001]，[(1)000, 0100][(1) 000, 0000][(0) 000, 0001]，[(1) 000, 0101][(1) 000, 0000][(0) 000, 0001]</p>

      <p class="p">供需12 个Byte。</p>

      <p class="p">如果应用差值规则来存储，需要的空间如下：</p>

      <p class="p">[(1) 000, 0010][(1) 000, 0000][(0) 000, 0001]，[(0) 000, 0001]，[(0) 000, 0001]，[(0) 000, 0001]共需6 个Byte。</p>

      <p class="p">大大缩小了存储空间，而且无论是文档ID，还是词在文档中的位置，都是按从小到大的顺序，逐渐增大的。</p>

    </div>

    <div class="section"><h2 class="title sectiontitle">或然跟随规则(A, B?)</h2>
      
      <p class="p">Lucene 的索引结构中存在这样的情况，某个值A 后面可能存在某个值B，也可能不存在，需要一个标志来表示后面是否跟随着B。</p>

      <p class="p">一般的情况下，在A 后面放置一个Byte，为0 则后面不存在B，为1 则后面存在B，或者0则后面存在B，1 则后面不存在B。</p>

      <p class="p">但这样要浪费一个Byte 的空间，其实一个Bit 就可以了。</p>

      <p class="p">在Lucene 中，采取以下的方式：A 的值左移一位，空出最后一位，作为标志位，来表示后面是否跟随B，所以在这种情况下，A/2 是真正的A 原来的值。</p>

      <p class="p"><img class="image" src="../../images/chapter02_03_image03.png" alt="移位"/></p>

      <p class="p">如果去读Apache Lucene - Index File Formats 这篇文章，会发现很多符合这种规则的：</p>

      <div class="p"><ul class="ul">
          <li class="li">.frq 文件中的DocDelta[, Freq?]，DocSkip,PayloadLength?</li>

          <li class="li">.prx 文件中的PositionDelta,Payload?</li>

          <li class="li">当然还有一些带?的但不属于此规则的：</li>

          <li class="li">.frq 文件中的SkipChildLevelPointer?，是多层跳跃表中，指向下一层表的指针，当然如果是最后一层，此值就不存在，也不需要标志。</li>

          <li class="li">.tvf 文件中的Positions?, Offsets?。<ul class="ul">
              <li class="li">在此类情况下，带?的值是否存在，并不取决于前面的值的最后一位。</li>

              <li class="li">而是取决于Lucene 的某项配置，当然这些配置也是保存在Lucene 索引文件中的。</li>

              <li class="li">如 Position 和Offset 是否存储， 取决于.fnm 文件中对于每个域的配置(TermVector.WITH_POSITIONS 和TermVector.WITH_OFFSETS)</li>

            </ul>
</li>

        </ul>
</div>

      <p class="p">为什么会存在以上两种情况，其实是可以理解的：</p>

      <div class="p"><ul class="ul">
          <li class="li">对于符合或然跟随规则的，是因为对于每一个A，B 是否存在都不相同，当这种情况大量存在的时候，从一个Byte 到一个Bit 如此8 倍的空间节约还是很值得的。</li>

          <li class="li">对于不符合或然跟随规则的，是因为某个值的是否存在的配置对于整个域(Field)甚至整个索引都是有效的，而非每次的情况都不相同，因而可以统一存放一个标志。</li>

        </ul>
</div>

    </div>

    <div class="section"><h2 class="title sectiontitle">跳跃表规则(Skip list)</h2>
      
      <p class="p">为了提高查找的性能，Lucene 在很多地方采取的跳跃表的数据结构。</p>

      <p class="p">跳跃表(Skip List)是如图的一种数据结构，有以下几个基本特征：</p>

      <div class="p"><ul class="ul">
          <li class="li">元素是按顺序排列的，在Lucene 中，或是按字典顺序排列，或是按从小到大顺序排列。</li>

          <li class="li">跳跃是有间隔的(Interval)，也即每次跳跃的元素数，间隔是事先配置好的，如图跳跃表的间隔为3。</li>

          <li class="li">跳跃表是由层次的(level)，每一层的每隔指定间隔的元素构成上一层，如图跳跃表共有2 层。</li>

        </ul>
</div>

      <p class="p"><img class="image" src="../../images/chapter02_03_image04.png" alt="跳跃表规则"/></p>

      <p class="p">需要注意一点的是，在很多数据结构或算法书中都会有跳跃表的描述，原理都是大致相同的，但是定义稍有差别：</p>

      <div class="p"><ul class="ul">
          <li class="li">对间隔(Interval)的定义： 如图中，有的认为间隔为2，即两个上层元素之间的元素数，不包括两个上层元素；有的认为是3，即两个上层元素之间的差，包括后面上层元素，不包括前面的上层元素；有的认为是4，即除两个上层元素之间的元素外，既包括前面，也包括后面的上层元素。Lucene 是采取的第二种定义。</li>

          <li class="li">对层次(Level)的定义：如图中，有的认为应该包括原链表层，并从1 开始计数，则总层次为3，为1，2，3 层；有的认为应该包括原链表层，并从0 计数，为0，1，2 层；有的认为不应该包括原链表层，且从1 开始计数，则为1，2 层；有的认为不应该包括链表层，且从0 开始计数，则为0，1 层。Lucene 采取的是最后一种定义。</li>

        </ul>
</div>

      <p class="p">跳跃表比顺序查找，大大提高了查找速度，如查找元素72，原来要访问2，3，7，12，23，37，39，44，50，72 总共10 个元素，应用跳跃表后，只要首先访问第1 层的50，发现72大于50，而第1 层无下一个节点，然后访问第2 层的94，发现94 大于72，然后访问原链表的72，找到元素，共需要访问3 个元素即可。</p>

      <p class="p">然而Lucene 在具体实现上，与理论又有所不同。</p>

    </div>

    <div class="section">
      <p class="p"><a class="xref" href="http://www.ossez.com/forum.php?mod=viewthread&amp;tid=18391&amp;fromuid=426" target="_blank">http://www.ossez.com/forum.php?mod=viewthread&amp;tid=18391&amp;fromuid=426</a></p>

    </div>

  </div>

<div class="related-links">
<div class="familylinks">
<div class="parentlink"><strong>父主题：</strong> <a class="link" href="../../tasks/chapter02/chapter02.html">Lucene的总体架构与代码</a></div>
</div>
</div>

</body>
</html>